
import java.util.*;
public class DeLinkedDemo {
    public static void main(String[] args) {
//        int n = 10;
//        int[] height = new int[]{1,7,3,2,4,5,8,2,7};
//        int re = maxArea(height);
//        System.out.println("re = " + re);
        int num[] = new int[]{1,2,4,4,1,1,1};
//        ArrayList<ArrayList<Integer>> result = threeSum(num);
//        System.out.println("result.toString() = " + result.toString());
        int target = 9;
//        int x = ClosestSum(num,target);
//        int x = reArrangeArray(num);
//        long x = maxWater(num);
        int x = minSubarray(num,target);
        System.out.println("x = " + x);

    }

    private static int minSubarray(int[] num, int target) {
//        int minLength = Integer.MAX_VALUE;
//        for (int i = 0; i < num.length; i++) {
//            int sum = num[i];
//            int len = 1;
//            for (int j = i+1; j < num.length; j++) {
//                sum+=num[j];
//                len++;
//                if(sum >= target){
//                    minLength = Math.min(len,minLength);
//                    break;
//                }
//            }
//        }
//        return minLength;
        int l = 0,r = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        while (r < num.length){
            sum += num[r];
            if(target <= sum){
                minLen = Math.min(minLen,r-l+1);
                sum = sum - num[l]-num[r];
                l = l+1;
                continue;
            }
            r++;
        }
        return minLen;
    }

    private static long maxWater(int[] num) {
        int l = 0 ,r = num.length-1;
        int result = 0;
        if(num.length == 0)
            return 0;
        int maxL = 0,maxR = 0;
        while (l < r){
            maxL = Math.max(maxL,num[l]);
            maxR = Math.max(maxR,num[r]);
            if(num[l] < num[r]){
                result += maxL - num[l];
                l = l+1;
            }else{
                result += maxR - num[r];
                r = r-1;
            }
        }
        return result;
    }

    private static int reArrangeArray(int[] num) {
        ArrayList<Integer> result = new ArrayList<>();
        HashSet<Integer> h = new HashSet<>();
        return 0;
    }

    private static int ClosestSum(int[] num, int target) {
        Arrays.sort(num);
        int min = Integer.MAX_VALUE;
        int result = min;
        for (int i = 0; i < num.length; i++) {
            int l = i+1 , r = num.length-1;
            while (l < r){
                int res = num[i] + num[l] +num[r];
                if(min > Math.abs(target-res)){
                    min = Math.abs(target-res);
                    result = res;
                    l = l+1;
                }else if(target > res){
                    l = l+1;
                }else{
                    r = r-1;
                }
            }
        }
        return result;
    }

    private static ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
//        Arrays.sort(num);
//        for (int i = 0; i < num.length; i++) {
//            int val = -num[i];
//            int l = i+1,r = num.length-1;
//            while (l < r){
//                ArrayList<Integer> second = new ArrayList<>();
//                if(num[l]+num[r] == val){
//                    second.add(num[i]);
//                    second.add(num[l]);
//                    second.add(num[r]);
//                    boolean contains = result.contains(second);
//                    if (!contains)
//                    result.add(second);
//                    l = l+1;
//                }else if(num[l]+num[r] < val){
//                    l = l+1;
//                }else{
//                    r = r-1;
//                }
//            }
//        }
//        return result;
        for (int i = 0; i < num.length; i++) {
            int val = num[i];
            HashMap<Integer,Integer> hashMap = new HashMap<>();
            for (int j = i+1; j < num.length; j++) {
                System.out.println("hashMap = " + hashMap);
                if(hashMap.containsValue(0-(val+num[j]))) {
                    ArrayList<Integer> second = new ArrayList<>();
                    second.add(val);
                    second.add(num[j]);
                    second.add(0 - (val + num[j]));
                    Collections.sort(second);
                    if(!result.contains(second)){
                        result.add(second);
                    }
                }else{
                    hashMap.put(j,num[j]);
                }
            }
        }
        System.out.println("result.toString() = " + result.toString());
        Collections.sort(result, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
                for (int i = 0; i < o1.size() && i < o2.size(); i++) {
                    if(o1.get(i) > o2.get(i)){
                        return 1;
                    }else if(o1.get(i) > o2.get(i)){
                        return -1;
                    }
                }
                return 0;
            }
        });
        System.out.println("result.toString() = " + result.toString());
        return result;
    }

    private static int maxArea(int[] height) {
        int max = 0;
        int l = 0 ,r = height.length-1;
        if(height.length<2) return 0;
        while (l <= r){
            int x = (height[l] < height[r] ? height[l] : height[r])*(r-l);
            max = max < x ? x:max;
            if(height[l] < height[r]){
                l=l+1;
            }else {
                r= r-1;
            }
        }
        return max;
    }

}
